СКІНЧЕННІ АВТОМАТИ

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
ТГВ
Кафедра:
Кафедра САПР

Інформація про роботу

Рік:
2010
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Лiнгвiстичне забезпечення САПР
Група:
КН-413

Частина тексту файла

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ Національний університет «Львівська політехніка» Кафедра САПР Звіт до Лабораторної роботи №2 на тему: СКІНЧЕННІ АВТОМАТИ з курсу: «Лінгвістичне забезпечення САПР» 1. МЕТА РОБОТИ Навчитися моделювати роботу розпізнавача за допомогою скінченного автомата. 2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ В основі побудові компіляторів лежить теорія автоматів. Автомат – це нереально існуючий пристрій, а деяка математична модель, властивості і поведінку якої можна вивчити і яку можна імітувати на реальній ЕОМ. Скінченний автомат – це найпростіша з моделей теорії автоматів. Скінченним називається автомат, у якому множина внутрішніх станів і множина вхідних значень є скінченними множинами. Скінченний розпізнавач – це модель пристрою із скінченним числом станів, які відрізняють правильно утворенні ланцюжки символів від неправильних (недопустимих). Вхідна стрічка – це послідовність комірок, кожна комірка містить тільки один символ із скінченного вхідного алфавіту. Крайню ліву і крайню праву комірки можуть займати кінцеві маркери. Вхідна головка у кожний момент часу читає одну вхідну комірку. Пам'ять розпізнавача – це будь-яке сховище інформації або даних. Оскільки алфавіт скінченний, то об’єм пам’яті скінченний. Керуючий пристрій є ядром розпізнавача. Це програма, яка керує роботою (поведінкою) розпізнавача. Керуючий пристрій – це скінченна множина станів разом з відображенням, яке описує як змінюється стани відповідно до поточного вхідного символу та інформацією, добутою із пам’яті. Роботу розпізнавача можна відобразити в термінах його конфігурації: 1. Стан керуючого пристрою; 2. Вміст вхідної стрічки і положення вхідної головки; 3. Вміст пам’яті; Конфігурація є початковою, якщо керуючий пристрій знаходиться у заданому початковому стані, вхідна головка може читати крайній лівий символ у стрічці і пам'ять має наперед установленний вміст. Конфігурація є кінцевою, якщо керуючий пристрій знаходиться в одному з наперед визначених множиною кінцевих станів, а вхідна головка може читати правий кінцевий маркер, або вразі його відсутності, вона зійшла з правого кінця вхідної стрічки. Формально скінченний розпізнавач визначається за п’ятьма характеристиками: 1. Скінченною множиною станів ; 2. Скінченним вхідним алфавітом ; 3. Множиною переходів , які відображають поведінку керуючого пристрою; 4. Початковим станом ; 5. Множиною кінцевих станів . Тобто скінченний автомат  описується як . ПРИКЛАД ПОБУДОВИ СКІНЧЕННОГО АВТОМАТА Прикладом скінченного автомата може контролер непарності «1» в ланцюжку символів, що складається з нулів і одиниць. Скінченний автомат буде допускати усі ланцюжки, які містять непарну кількість «1» і відкидати ті з них, які містять парну кількість «1». Вхідним алфавітом  такого автомата буде множина {0, 1}. Множина станів  буде складатись із двох станів ПАР і НЕПАР. Початковим станом  буде стан ПАР. При читанні наступного вхідного символу стан автомата змінюється. Новий його стан залежить від вхідного символу і поточного символу. Функція переходів  буде мати такий вигляд: (ПАР, 0)=ПАР (ПАР, 1)=НЕПАР (НЕПАР, 0)=НЕПАР (НЕПАР, 1)=ПАР Кінцевий (допускаючим) станом  є НЕПАР. Ланцюжок 1101 допускається автоматом, оскільки останнім є допускаючий стан НЕПАР. Іншою є ситуація при обробці ланцюжка 101, він відкидається, оскільки його кінцевим станом є недопустимий стан ПАР. Один із зручних методів подання скінченного автомата є таблиця переходів. Правила побудови таблиці такі: 1. Стовпці помічено символами вхідного алфавіту. 2. Рядки помічено символами станів. 3. Елементи таблиці є символами нових станів, які визначаються вхідним символом і попереднім станом. 4. Перший рядок помічено символом початкового стану. 5. Рядки, які відповідають допускаючим станам, помічені справа одиницями: рядки, які відкидаються автоматом, помічаються справа нулями. Для нашого автомата таблиця переходів показана на рис. 1. Крім табличного подання, скінченний автомат можна подати діаграмою (або графом) переход...
Антиботан аватар за замовчуванням

17.07.2020 15:07

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини